#pragma once

#include <functional>
#include <utility>
#include <limits>
/**
 * 堆：
 *  由一个数组建立的二叉堆树(完全二叉树).
 *  所有结点都满足以下条件：
 *      A[Parent[i]] >= A[i] or A[Parent[i]] <= A[i] or 
 *  其规则，数组首元素为根结点，除最底层的叶节点外，该树是完全填满的，而且是从左到右填充.
 *  并且分为最大堆与最小堆.
 *  并且具有以下特性：
 *      左结点索引计算=> i * 2
 *      右结点索引计算=> i * 2 + 1
 *      父结点索引计算=> i / 2
 *      最大堆=>其根结点为最大元素
 *      最小堆=>其根结点为最小元素
 *      堆树高=>渐近边界(lgn)
 * 
 * 通常使用最小堆来构造优先队列.
 *       0                  1
 *     1   2     =>      2     3
 *    3 4 5 6          4   5 6   7
 * 对应的数组如下：
 *  [0,1,2,3,4,5,6]
 * 由此可见需要进行索引转换，即：
 *  从数组索引转换成数学索引并在数学索引的基础上进行计算，再将数学索引转成数组索引返回.
 *  or
 *  leftIndex = i * 2 + 1
 *  rightIndex = leftIndex + 1
 *  parent = (i - 1) / 2
 * 
 * 当高度为h时最多有->　f(h) = f(h - 1) + 2^h个结点，此时也就是完美二叉树
 *          最少有->  f(h) = f(h - 1) + 1个结点，此时为完全二叉树
 * 推导公式：
 *      f(0) = 2^0 = 1
 *      f(1) = f(0) + 2^1
 *      f(2) = f(1) + 2^2
 *      f(3) = f(2) + 2^3
 *            ||
 *      f(h) = f(h - 1) + 2^h
 * 
 * 叶结点下标：
 *      数学索引 => (A.length / 2) + 1....n
 *          相应最后一个具有子结点的元素下标：(A.length / 2)
 *      数组索引 => (A.length - 1) / 2 + 1....n
 *          相应最后一个具有子结点的元素下标：(A.length - 1) / 2
 *      
 */


/**
 * 外部传入的是数组索引(从0开始),返回nIndex元素的父索引值
 */
int ParentIndex(int nIndex){
    if(nIndex == 0)
        return 0;
    
    return (nIndex - 1) / 2;
}

/**
 * 返回nIndex元素的左子元素索引
 */
int LeftIndex(int nIndex){
    return nIndex * 2 + 1;
}

/**
 * 返回nIndex元素的右子元素索引
 */
int RightIndex(int nIndex){
    return LeftIndex(nIndex) + 1;
}

/**
 * 返回最后一个具有子结点的结点下标.
 * @param nLen是最后一个元素的数组索引
 */
int LastChildNodeIndex(int nLen){
    return (nLen - 1) / 2;
}

/**
 * 维护从nIndex结点开始的堆性质
 * @param nIndex是数组某元素索引
 * @param nLen是最后一个元素的数组索引
 */
template<typename T, typename compare = std::greater<T>>
void HeapCheck(T* pElems, int nIndex, int nLen){

    int nLeftIndex = LeftIndex(nIndex);
    int nRightIndex = RightIndex(nIndex);

    compare comp;
    int nTarget;
    if(nLeftIndex <= nLen && comp(pElems[nLeftIndex], pElems[nIndex]))
        nTarget = nLeftIndex;
    else
        nTarget = nIndex;

    if(nRightIndex <= nLen && comp(pElems[nRightIndex], pElems[nTarget]))
        nTarget = nRightIndex;
    
    if(nTarget != nIndex){
        std::swap<T>(pElems[nTarget], pElems[nIndex]);
         HeapCheck<T, compare>(pElems, nTarget, nLen);
    }
}

/**
 * 构建堆结构
 * @param nLen是最后一个元素的数组索引
 * @tempParam compare 更改比较方式可改变为 最大堆 or 最小堆
 * 从最后一个具有子结点的元素索引开始维护堆性质.
 */
template<typename T, typename compare = std::greater<T>>
void BuildHeap(T* pElems, int nLen){
    int lastNode = LastChildNodeIndex(nLen);
    for(int i = lastNode; i >= 0; --i){
        HeapCheck<T, compare>(pElems, i, nLen);
    }
}

/**
 * 进行堆排序.
 * @param nLen是最后一个元素的数组索引
 * @tempParam compare 更改比较方式可改变为 最大堆排序 or 最小堆排序
 * 每次取出根结点(使得根结点与最后的叶结点交换，并缩短相应的视野)
 */
template<typename T, typename compare = std::greater<T>>
void HeapSort(T* pElems, int nLen){
    BuildHeap<T, compare>(pElems, nLen);
    //[[
    for(int i = nLen; i >= 0; ){
        std::swap<T>(pElems[0], pElems[i]);
        HeapCheck<T, compare>(pElems, 0, --i);
    }
    //]]
    //以上代码可转换成:
    // std::pair<int*, int> ItemEntry;
    // while((ItemEntry = PopHeapFirst(pElems, nLen)).first != nullptr){
    //     nLen = ItemEntry.second;
    // }                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
}

/**
 * 返回堆首元素，此为优先队列中最优.
 * 作用在最大堆 or 最小堆.
 */
template<typename T>
T* HeapFirst(T* pElems){
    return &pElems[0];
}


/**
 * 取出堆首元素(队列中最优).
 * @param pElems 指向数组的指针
 * @param nLen 最后一个有效元素的索引
 * 
 * 不应传入为负数的nLen，并非真的删除数组中的元素只是缩小了视界范围.
 * 所以返回元素的生命周期等于此数组的生命周期(应在第一时间将其拷贝，防止被插入操作覆盖).
 * 若返回值中第二个参数为负数(second < 0)则表明此优先队列中没有可用元素.
 * 需要注意当nLen == 0时返回的second为-1.
 * 在正常使用的情况下，不建议使用通过调用这个函数排序．
 */
template<typename T, typename compare = std::greater<T>>
std::pair<T*, int> PopHeapFirst(T* pElems, int nLen){
    if(nLen < 0)
        return {nullptr, nLen};
    else if(nLen == 0){
        return {&pElems[0], -1};
    }else{
        std::swap<T>(pElems[0], pElems[nLen]);
        HeapCheck<T, compare>(pElems, 0, nLen - 1);
        return {&pElems[nLen], nLen - 1};
    }
}

/**
 * 提升堆中元素级别.
 * @param nIndex相应元素的下标索引．
 * 
 * @return 提升成功返回true，当提升为的值不满足比较式时返回false．
 */
template<typename T, typename compare = std::greater<T>>
bool UpgradeHeapElement(T* pElems, int nIndex, const T& value){
    compare comp;
    if(comp(pElems[nIndex], value))
        return false;
    
    pElems[nIndex] = const_cast<T&>(value);
    
    while(nIndex > 0 && comp(pElems[nIndex], pElems[ParentIndex(nIndex)])){
        std::swap<T>(pElems[nIndex], pElems[ParentIndex(nIndex)]);
        nIndex = ParentIndex(nIndex);
    }
    return true;
}

/**
 * 向堆中添加新的元素.
 * @param HeapTye 当true时使用的是最大堆反之则是最小堆．
 * @param value 需要插入的值.
 * @param nLen　当前已经存在的最后一个元素的下标索引，若堆中不存元素在则为-1.
 * @return 返回值为一对儿结果，first 表示是否插入成功，second表示堆中最后一个元素.
 */
template<typename T, typename compare = std::greater<T>, bool HeapType = true>
std::pair<bool, int> InsertHeapElement(T* pElems, const T& value, int nLen){
    nLen += 1;
    if(HeapType)
        pElems[nLen] = std::numeric_limits<T>::min();
    else
        pElems[nLen] = std::numeric_limits<T>::max();
        
    bool bResult = UpgradeHeapElement<T, compare>(pElems, nLen, value);
    if(!bResult) --nLen;
    return {bResult, nLen};
}

/**
 * 删除堆中元素.
 * @param nIndex需要删除的下标索引.
 * @param nLen则为最后一个有效元素的索引值
 * @return 返回堆中最后一个有效元素的索引.
 * 
 * 通过将删除的元素与最后一个有效元素交换位置并维护堆的性质以达到删除的目的.
 */
template<typename T, typename compare = std::greater<T>>
int DeleteHeapElement(T* pElems, int nIndex, int nLen){
    std::swap<T>(pElems[nIndex], pElems[nLen]);
    HeapCheck<T, compare>(pElems, nIndex, --nLen);

    return nLen;
}

#include <vector>
#include <cassert>

/**
 * 此最大、最小堆不是线程安全的，不应该传入针指类型，除智能指针外.
 */
template<typename T, typename compare = std::greater<T>>
class Heap{
public:
    Heap(T* pElems, int nSize):m_nSize(nSize){
        if(pElems && m_nSize > 0){
            m_vecElems.resize(m_nSize);
            for(int i = 0; i < m_nSize; ++i){
                assert(pElems[i]);
                m_vecElems[i] = pElems[i];
            }
        }

        m_nLastIndex = m_vecElems.size() - 1;
        ::BuildHeap<T, compare>(m_vecElems.data(), m_nLastIndex);
    }

    Heap(int nSize):m_nSize(nSize), m_nLastIndex(-1){
        assert(m_nSize);
        m_vecElems.resize(m_nSize);
    }

    ~Heap(){

    }

    template<bool bHeapType = true>
    bool Insert(const T& value){
        if(IsFullCheck()){
            auto result = ::InsertHeapElement<T, compare, bHeapType>(m_vecElems.data(), value, m_nLastIndex);
            m_nLastIndex = result.second;
            return true;
        }
        return false;
    }

    /**
     * @return 结果需要在第一时间拷贝，其存在的生命周期主要看Insert在什么时间将其覆盖，
     *          不能依赖其生命周期.
     */
    T* PopFirst(){
        if(IsEmptyCheck()) return nullptr;

        auto result = ::PopHeapFirst<T, compare>(m_vecElems.data(), m_nLastIndex);
        m_nLastIndex = result.second;
        return result.first;
    }

    bool IsFullCheck(){
        return m_nSize > m_nLastIndex ? true : false;
    }

    bool IsEmptyCheck(){
        return m_nLastIndex < 0 ? true : false;
    }

private:
    std::vector<T> m_vecElems;
    int m_nLastIndex;
    int m_nSize;
};